package hero.mps.leet_code_18;

import java.util.*;

public class Sum4 {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < nums.length - 3; i++) {
            // 如果当前数字与前一个数字相同，则跳过此次循环
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1; j < nums.length - 2 ; j++) {
                // 如果当前数字与前一个数字相同，则跳过此次循环
                if ( j > i + 1 && nums[j] == nums[j - 1]) continue;
                int left = j + 1, right = nums.length - 1;
                while (left < right) {
                    long sum = (long)nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum  == target) {
                        // 将找到的四个数添加到结果列表中
                        res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        // 跳过重复的数字
                        while (left < right && nums[left] == nums[left + 1]) left++;
                        while (left < right && nums[right] == nums[right - 1]) right--;
                        left++;
                        right--;
                    } else if (sum < target) {
                        // 如果和小于目标值，则将左指针右移
                        left ++;
                    } else {
                        // 如果和大于目标值，则将右指针左移
                        right --;
                    }
                }
            }
        }
        return res;
    }

    public List<List<Integer>> fourSum1(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;

        // 遍历数组，从第一个数开始
        for (int i = 0; i < n - 3; i++) {
            // 如果当前数与前一个数相同，则跳过
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            // 如果当前数与后面三个数的和已经大于目标值，则无需继续遍历，直接跳出循环
            if ((long)nums[i] + nums[i + 1] + nums[i + 2] + nums[ i + 3] > target) break;

            // 如果当前数与最后三个数的和仍然小于目标值，则跳过当前数
            if ((long)nums[i] + nums[n - 1] + nums[n - 2] + nums[n - 3] < target) continue;

            // 遍历数组，从i+1开始
            for (int j = i + 1; j < n -2; j++) {
                // 如果当前数与前一个数相同，则跳过
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;

                // 如果当前数与后面两个数的和已经大于目标值，则无需继续遍历，直接跳出循环
                if ((long)nums[i] + nums[j] + nums[j+1] + nums[j+2] > target) break;

                // 如果当前数与最后两个数的和仍然小于目标值，则跳过当前数
                if ((long)nums[i] + nums[j] + nums[n-1] + nums[n-2] < target) continue;

                int left = j+1, right = n-1;

                // 使用双指针法在j+1和n-1之间查找另外两个数
                while (left < right) {
                    long sum = (long)nums[i] + nums[j] + nums[left] + nums[right];

                    // 如果找到了符合条件的四个数
                    if (sum == target) {
                        // 将结果添加到结果列表中
                        res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));

                        // 跳过重复的数字
                        while (left < right && nums[left] == nums[left+1]) left++;
                        while (left < right && nums[right] == nums[right-1]) right--;

                        // 移动指针继续查找
                        left++;
                        right--;
                    }
                    // 如果和小于目标值，则将左指针右移
                    else if (sum < target){
                        left++;
                    }
                    // 如果和大于目标值，则将右指针左移
                    else {
                        right--;
                    }
                }
            }
        }

        // 返回结果列表
        return res;
    }

    public List<List<Integer>> fourSum2(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        Set<List<Integer>> resSet = new HashSet<>();
        Map<Long, List<int[]>> twoSumMap = new HashMap<>();
        int n = nums.length;

        // 构建twoSumMap，记录数组中两个数之和以及对应的下标
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                long sum = (long)nums[i] + nums[j];
                if (!twoSumMap.containsKey(sum)) {
                    twoSumMap.put(sum, new ArrayList<>());
                }
                twoSumMap.get(sum).add(new int[]{i, j});
            }
        }

        // 遍历数组，寻找四个数之和等于target的组合
        for (int i = 0;  i < n-3; i++) {
            if (i > 0 && nums[i] == nums[i-1]) continue;
            for (int j = i+1; j < n-2; j++) {
                if (j > i+1 && nums[j] == nums[j-1]) continue;

                // 计算剩余需要匹配的和
                long remain = (long) target - nums[i] - nums[j];

                // 查找是否存在和为remain的两个数
                if (twoSumMap.containsKey(remain)) {
                    for (int[] pair :  twoSumMap.get(remain)) {
                        int k = pair[0], l = pair[1];

                        // 判断找到的下标是否符合要求（k>j）
                        if (k > j) {
                            List<Integer> resList = Arrays.asList(nums[i], nums[j], nums[k], nums[l]);

                            // 添加到结果集合中，并检查是否重复
                            if (resSet.add(resList)) {
                                res.add(resList);
                            }
                        }
                    }
                }

                // 跳过重复的元素
                while (j < n - 2 && nums[j] == nums[j+1]) j++;
            }

            // 跳过重复的元素
            while (i < n -3 && nums[i] == nums[i+1]) i++;
        }

        return res;
    }

    public static void main(String[] args) {
        System.out.println(new Sum4().fourSum2(new int[]{1, 0, -1, 0, -2, 2}, 0));
    }
}
